Search

Interpreting a node-link graph is enhanced if similar subgraphs (or motifs) are depicted in a similar manner; that is, they have the same visual form. Small motifs within graphs may be perceived to be identical when they are structurally dissimilar, or may be perceived to be dissimilar when they are identical. This issue primarily relates to the Gestalt principle of similarity, but may also include an element of quick, low-level pattern-matching. We believe that if motifs are identical, they should be depicted identically; if they are nearly-identical, they should be depicted nearly-identically. This principle is particularly important in domains where motifs hold meaning and where their identification is important. We identified five small motifs: bi-cliques, cliques, cycles, double-cycles, and stars. For each, we defined visual variations on two dimensions: same or different structure, same or different shape. We conducted a crowd-sourced empirical study to test the perception of similarity of these varied motifs, and found that determining whether motifs are identical or similar is affected by both shape and structure., Comment: Appears in the Proceedings of the 31st International Symposium on Graph Drawing and Network Visualization (GD 2023)

Metro or transit maps, are schematic representations of transit networks to facilitate effective route-finding. These maps are often advertised on a web page or pamphlet highlighting routes from source to destination stations. To visually support such route-finding, designers often distort the layout by embedding symbolic shapes (e.g., circular routes) in order to guide readers' attention (e.g., Moscow map and Japan railway map). However, manually producing such maps is labor-intensive and the effect of shapes remains unclear. In this paper, we propose an approach to generalize such mixed metro maps that take user-defined shapes as an input. In this mixed design, lines that are used to approximate the shapes are arranged symbolically, while the remaining lines follow classical layout convention. A three-step algorithm, including (1) detecting and selecting routes for shape approximation, (2) shape and layout deformation, and (3) aligning lines on a grid, is integrated to guarantee good visual quality. Our contribution lies in the definition of the mixed metro map problem and the formulation of design criteria so that the problem can be resolved systematically using the optimization paradigm. Finally, we evaluate the performance of our approach and perform a user study to test if the embedded shapes are recognizable or reduce the map quality., Comment: 19 Pages, 20 Figures, to be published in the proceedings of Pacific Graphics 2022

Schematic maps are in daily use to show the connectivity of subway systems and to facilitate travellers to plan their journeys effectively. This study surveys up-to-date algorithmic approaches in order to give an overview of the state of the art in schematic network mapping. The study investigates the hypothesis that the choice of algorithmic approach is often guided by the requirements of the mapping application. For example, an algorithm that computes globally optimal solutions for schematic maps is capable of producing results for printing, while it is not suitable for computing instant layouts due to its long running time. Our analysis and discussion, therefore, focus on the computational complexity of the problem formulation and the running times of the schematic map algorithms, including algorithmic network layout techniques and station labeling techniques. The correlation between problem complexity and running time is then visually depicted using scatter plot diagrams. Moreover, since metro maps are common metaphors for data visualization, we also investigate online tools and application domains using metro map representations for analytics purposes, and finally summarize the potential future opportunities for schematic maps., Comment: The 2nd Schematic Mapping Workshop

In this paper, we present a new workflow for the computer-aided generation of physicalizations, addressing nested configurations in anatomical and biological structures. Physicalizations are an important component of anatomical and biological education and edutainment. However, existing approaches have mainly revolved around creating data sculptures through digital fabrication. Only a few recent works proposed computer-aided pipelines for generating sculptures, such as papercrafts, with affordable and readily available materials. Papercraft generation remains a challenging topic by itself. Yet, anatomical and biological applications pose additional challenges, such as reconstruction complexity and insufficiency to account for multiple, nested structures--often present in anatomical and biological structures. Our workflow comprises the following steps: (i) define the nested configuration of the model and detect its levels, (ii) calculate the viewpoint that provides optimal, unobstructed views on inner levels, (iii) perform cuts on the outer levels to reveal the inner ones based on the viewpoint selection, (iv) estimate the stability of the cut papercraft to ensure a reliable outcome, (v) generate textures at each level, as a smart visibility mechanism that provides additional information on the inner structures, and (vi) unfold each textured mesh guaranteeing reconstruction. Our novel approach exploits the interactivity of nested papercraft models for edutainment purposes., Comment: 13 pages

The splitting number of a graph $G=(V,E)$ is the minimum number of vertex splits required to turn $G$ into a planar graph, where a vertex split removes a vertex $v \in V$, introduces two new vertices $v_1, v_2$, and distributes the edges formerly incident to $v$ among its two split copies $v_1, v_2$. The splitting number problem is known to be NP-complete. In this paper we shift focus to the splitting number of graph drawings in $\mathbb R^2$, where the new vertices resulting from vertex splits can be re-embedded into the existing drawing of the remaining graph. We first provide a non-uniform fixed-parameter tractable (FPT) algorithm for the splitting number problem (without drawings). Then we show the NP-completeness of the splitting number problem for graph drawings, even for its two subproblems of (1) selecting a minimum subset of vertices to split and (2) for re-embedding a minimum number of copies of a given set of vertices. For the latter problem we present an FPT algorithm parameterized by the number of vertex splits. This algorithm reduces to a bounded outerplanarity case and uses an intricate dynamic program on a sphere-cut decomposition., Comment: Appeared in the proceedings of the 30th International Symposium on Graph Drawing and Network Visualization (GD 2022)

We consider the problem of untangling a given (non-planar) straight-line circular drawing $\delta_G$ of an outerplanar graph $G=(V, E)$ into a planar straight-line circular drawing by shifting a minimum number of vertices to a new position on the circle. For an outerplanar graph $G$, it is clear that such a crossing-free circular drawing always exists and we define the circular shifting number shift$(\delta_G)$ as the minimum number of vertices that are required to be shifted in order to resolve all crossings of $\delta_G$. We show that the problem Circular Untangling, asking whether shift$(\delta_G) \le K$ for a given integer $K$, is NP-complete. For $n$-vertex outerplanar graphs, we obtain a tight upper bound of shift$(\delta_G) \le n - \lfloor\sqrt{n-2}\rfloor -2$. Based on these results we study Circular Untangling for almost-planar circular drawings, in which a single edge is involved in all the crossings. In this case, we provide a tight upper bound shift$(\delta_G) \le \lfloor \frac{n}{2} \rfloor-1$ and present a constructive polynomial-time algorithm to compute the circular shifting number of almost-planar drawings., Comment: 20 pages, 10 figures, extended version of ISAAC 2021 paper

The concept of multilayer networks has become recently integrated into complex systems modeling since it encapsulates a very general concept of complex relationships. Biological pathways are an example of complex real-world networks, where vertices represent biological entities, and edges indicate the underlying connectivity. For this reason, using multilayer networks to model biological knowledge allows us to formally cover essential properties and theories in the field, which also raises challenges in visualization. This is because, in the early days of pathway visualization research, only restricted types of graphs, such as simple graphs, clustered graphs, and others were adopted. In this paper, we revisit a heterogeneous definition of biological networks and aim to provide an overview to see the gaps between data modeling and visual representation. The contribution will, therefore, lie in providing guidelines and challenges of using multilayer networks as a unified data structure for the biological pathway visualization.

Route planning and navigation are common tasks that often require additional information on points of interest. Augmented Reality (AR) enables mobile users to utilize text labels, in order to provide a composite view associated with additional information in a real-world environment. Nonetheless, displaying all labels for points of interest on a mobile device will lead to unwanted overlaps between information, and thus a context-responsive strategy to properly arrange labels is expected. The technique should remove overlaps, show the right level-of-detail, and maintain label coherence. This is necessary as the viewing angle in an AR system may change rapidly due to users' behaviors. Coherence plays an essential role in retaining user experience and knowledge, as well as avoiding motion sickness. In this paper, we develop an approach that systematically manages label visibility and levels-of-detail, as well as eliminates unexpected incoherent movement. We introduce three label management strategies, including (1) occlusion management, (2) level-of-detail management, and (3) coherence management by balancing the usage of the mobile phone screen. A greedy approach is developed for fast occlusion handling in AR. A level-of-detail scheme is adopted to arrange various types of labels. A 3D scene manipulation is then built to simultaneously suppress the incoherent behaviors induced by viewing angle changes. Finally, we present the feasibility and applicability of our approach through one synthetic and two real-world scenarios, followed by a qualitative user study.

Graphs are by nature unifying abstractions that can leverage interconnectedness to represent, explore, predict, and explain real- and digital-world phenomena. Although real users and consumers of graph instances and graph workloads understand these abstractions, future problems will require new abstractions and systems. What needs to happen in the next decade for big graph processing to continue to succeed?, Comment: 12 pages, 3 figures, collaboration between the large-scale systems and data management communities, work started at the Dagstuhl Seminar 19491 on Big Graph Processing Systems, to be published in the Communications of the ACM

During the last decades, anatomy has become an interesting topic in education---even for laymen or schoolchildren. As medical imaging techniques become increasingly sophisticated, virtual anatomical education applications have emerged. Still, anatomical models are often preferred, as they facilitate 3D localization of anatomical structures. Recently, data physicalizations (i.e., physical visualizations) have proven to be effective and engaging---sometimes, even more than their virtual counterparts. So far, medical data physicalizations involve mainly 3D printing, which is still expensive and cumbersome. We investigate alternative forms of physicalizations, which use readily available technologies (home printers) and inexpensive materials (paper or semi-transparent films) to generate crafts for anatomical edutainment. To the best of our knowledge, this is the first computer-generated crafting approach within an anatomical edutainment context. Our approach follows a cost-effective, simple, and easy-to-employ workflow, resulting in assemblable data sculptures (i.e., semi-transparent sliceforms). It primarily supports volumetric data (such as CT or MRI), but mesh data can also be imported. An octree slices the imported volume and an optimization step simplifies the slice configuration, proposing the optimal order for easy assembly. A packing algorithm places the resulting slices with their labels, annotations, and assembly instructions on a paper or transparent film of user-selected size, to be printed, assembled into a sliceform, and explored. We conducted two user studies to assess our approach, demonstrating that it is an initial positive step towards the successful creation of interactive and engaging anatomical physicalizations.

Physical visualizations (i.e., data representations by means of physical objects) have been used for many centuries in medical and anatomical education. Recently, 3D printing techniques started also to emerge. Still, other medical physicalizations that rely on affordable and easy-to-find materials are limited, while smart strategies that take advantage of the optical properties of our physical world have not been thoroughly investigated. We propose the Anatomical Edutainer, a workflow to guide the easy, accessible, and affordable generation of physicalizations for tangible, interactive anatomical edutainment. The Anatomical Edutainer supports 2D printable and 3D foldable physicalizations that change their visual properties (i.e., hues of the visible spectrum) under colored lenses or colored lights, to reveal distinct anatomical structures through user interaction.

Do algorithms for drawing graphs pass the Turing Test? That is, are their outputs indistinguishable from graphs drawn by humans? We address this question through a human-centred experiment, focusing on `small' graphs, of a size for which it would be reasonable for someone to choose to draw the graph manually. Overall, we find that hand-drawn layouts can be distinguished from those generated by graph drawing algorithms, although this is not always the case for graphs drawn by force-directed or multi-dimensional scaling algorithms, making these good candidates for Turing Test success. We show that, in general, hand-drawn graphs are judged to be of higher quality than automatically generated ones, although this result varies with graph size and algorithm., Comment: Appears in the Proceedings of the 28th International Symposium on Graph Drawing and Network Visualization (GD 2020)

For decades, researchers in information visualisation and graph drawing have focused on developing techniques for the layout and display of very large and complex networks. Experiments involving human participants have also explored the readability of different styles of layout and representations for such networks. In both bodies of literature, networks are frequently referred to as being 'large' or 'complex', yet these terms are relative. From a human-centred, experiment point-of-view, what constitutes 'large' (for example) depends on several factors, such as data complexity, visual complexity, and the technology used. In this paper, we survey the literature on human-centred experiments to understand how, in practice, different features and characteristics of node-link diagrams affect visual complexity.

We report on the variation in the optical polarization of the blazar PKS 1749+096 observed in 2008--2015. The degree of polarization (PD) tends to increase in short flares having a time-scale of a few days. The object favors a polarization angle (PA) of $40^\circ$--$50^\circ$ at the flare maxima, which is close to the position angle of the jet ($20^\circ$--$40^\circ$). Three clear polarization rotations were detected in the negative PA direction associated with flares. In addition, a rapid and large decrease in the PA was observed in the other two flares, while another two flares showed no large PA variation. The light curve maxima of the flares possibly tend to lag behind the PD maxima and color-index minima. The PA became $-50^\circ$ to $-20^\circ$ in the decay phase of active states, which is almost perpendicular to the jet position angle. We propose a scenario to explain these observational features, where transverse shocks propagate along curved trajectories. The favored PA at the flare maxima suggests that the observed variations were governed by the variations in the Doppler factor, $\delta$. Based on this scenario, the minimum viewing angle of the source, $\theta_\mathrm{min}=4.8^\circ$--$6.6^\circ$, and the location of the source, $\Delta r\gtrsim 0.1$pc, from the central black hole were estimated. In addition, the acceleration of electrons by the shock and synchrotron cooling would have a time-scale similar to that of the change in $\delta$. The combined effect of the variation in $\delta$ and acceleration/cooling of electrons is probably responsible for the observed diversity of the polarization variations in the flares., Comment: 12 pages, 9 figures, accepted for publication in PASJ